package demo.DataStrucAndAlgo.HashTable;

import java.util.Scanner;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/28-07-28-11:21
 * @Description：demo.DataStrucAndAlgo.HashTable    哈希表（散列表）
 * 无头结点、
 */
/*
哈希表
    根据关键码进行数据访问的数据结构，通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，
    存放记录的数组叫做散列表
    数组+链表
    数组+二叉树
 */
/*
    哈希表和hashMap区别：
        哈希表，key、value不能为空，hashmap可以为空
*/
class Node{
    private int id;
    private int data;
    private Node next;

    public int getId() {
        return id;
    }

    public Node(int id, int data) {
        this.id = id;
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", data=" + data +
                '}';
    }
}
class linkedList{
    private Node root;
    public void add(Node node){
        if(isEmpty()){
            root = node;
            return;
        }
        Node temp = root;
        while(temp.getNext() !=null){
            temp = temp.getNext();
        }
        temp.setNext(node);
    }

    private boolean isEmpty() {
        return root == null;
    }

    public Node remove(){
        if(isEmpty()){
            throw new RuntimeException("当前列表为空，删除失败");
        }
        Node temp = root.getNext();
        if(root.getNext() == null){
            root = null;
            return temp;
        }
        while(temp.getNext().getNext() != null){
            temp = temp.getNext();
        }
        Node node = temp.getNext();
        temp.setNext(null);
        return node;
    }
    public Node remove(int id){
        if(isEmpty()){
            throw new RuntimeException("当前列表为空，删除失败");
        }
        Node temp = root;
        if(root.getId() == id){
            root = root.getNext();
            return temp;
        }else{
            Node temp2;
            while(temp.getNext() != null){
                temp2 = temp;
                temp = temp.getNext();
                if(temp.getId() == id){
                    temp2.setNext(temp.getNext());
                    return temp;
                }
            }
            return null;
        }
    }
    public void show(){
        Node temp = root;
        while(temp != null){
            System.out.print(" -> " + temp.toString());
            temp = temp.getNext();
        }

        System.out.println();
    }
    public Node find(int id){
        if(isEmpty()){
            return null;
        }
        Node temp = root;
        while(temp != null){
            if(temp.getId() == id){
                return temp;
            }
            temp = temp.getNext();
        }
        return null;
    }
}
class hashTable_use{
    int size;
    linkedList[] linkedTable;
    public hashTable_use(int size){
        this.size = size;
        linkedTable = new linkedList[size];
        for (int i = 0; i < size; i++) {
            linkedTable[i] = new linkedList();
        }
    }
    public void add(Node node){
        int id = node.getId() % size;
        linkedTable[id].add(node);
    }
    public Node remove(int id){
        int index = id % size;
        return linkedTable[index].remove(id);
    }
    public Node find(int id){
        int index = id % size;
        return linkedTable[index].find(id);
    }
    public void show(){
        for (int i = 0; i < size; i++) {
            System.out.print(i);
            linkedTable[i].show();
        }
    }
}
public class hashTable {
//    public static void main(String[] args) {
//        hashTable_use table = new hashTable_use(3);
//        table.add(new Node(1,1));
//        table.add(new Node(2,2));
//        table.add(new Node(3,3));
//        table.add(new Node(4,4));
//        table.add(new Node(5,5));
//        table.add(new Node(6,6));
//        table.add(new Node(7,7));
//        table.add(new Node(8,8));
//        table.show();
//        if(table.find(3) == null){
//            System.out.println("没有找到");
//        }else{
//            System.out.println("找到该结点了 + " + table.find(3));
//        }
//        table.remove(3);
//        System.out.println("-------------------------");
//        if(table.find(3) == null){
//            System.out.println("没有找到");
//        }else{
//            System.out.println("找到该结点了 + " + table.find(3));
//        }
//        table.show();
//        System.out.println("------------------------");
//        table.remove(4);
//        table.remove(2);
//        table.show();
//    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入你想要的散列表大小：");
        int size = sc.nextInt();
        hashTable_use table = new hashTable_use(size);
        int num,id,data;
        Node node;
        while(true){
            System.out.println("请输入你要进行的操作：0（退出） 1（添加数据） 2 （删除元素） 3（查找）4（展示所有元素）");
            num = sc.nextInt();
            if(num == 0){
                System.out.println("goodBye!");
                break;
            }else if(num == 1){
                System.out.print("请输入要插入的id和数据：（空格隔开）");
                id = sc.nextInt();
                data = sc.nextInt();
                node = new Node(id,data);
                table.add(node);
                System.out.println("添加成功");
            }else if(num == 2){
                System.out.print("请输入要删除的元素id： ");
                id = sc.nextInt();
                node = table.remove(id);
                if(node == null){
                    System.out.println("你要删除的元素不存在");
                }else{
                    System.out.println("你已成功删除元素：" + node);
                }
            }else if(num == 3){
                System.out.print("请输入你要查找的元素id：");
                id = sc.nextInt();
                node = table.find(id);
                if(node == null){
                    System.out.println("未找到你要的数据");
                }else{
                    System.out.println("你查找的数据为：" + node);
                }
            }else{
                System.out.println("-----------------------");
                table.show();
                System.out.println("---------------------------");
            }
        }
    }
}
